package com.lyq.leetcode.字母异位词分组49;

import java.util.*;

/**
 * @author lyq
 */
public class Main {

    public static void main(String[] args) {
        Main main = new Main();
        String[] array = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.printf("%s", main.groupAnagramsMap(array));
    }

    /**
     *进行对字符串内部排序，使字母异位词字符串相同，然后进行个数统计
     *
     * @param strs 字符串数组
     * @return 分组后的数组
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        String[] temp = Arrays.copyOf(strs,strs.length);
        for (int i = 0; i < temp.length; i++) {
            char[] charArray = temp[i].toCharArray();
            Arrays.sort(charArray);
            temp[i] = new String(charArray);
        }
        for (int i = 0; i < temp.length; i++){
            if (!Objects.equals(temp[i], "0")){
                List<String> temp2 = new ArrayList<>();
                temp2.add(strs[i]);
                for (int j = i+1; j < temp.length; j++) {
                    if (temp[i].equals(temp[j])){
                        temp2.add(strs[j]);
                        temp[j]="0";
                    }
                }
                res.add(temp2);
            }
        }
        return res;
    }

    /**
     *利用数据结构使查询效率为1
     *
     * @param strs 字符串数组
     * @return 分组后的数组
     */
    public List<List<String>> groupAnagramsMap(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>(1);
        for (String s:strs){
            char[] charArray = s.toCharArray();
            Arrays.sort(charArray);
            String str = new String(charArray);
            // 如果 map 中不存在该 key，则创建新的列表
            map.computeIfAbsent(str, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }
}
